1. Field of the Invention
The present invention relates to a load balancing method and apparatus in a symmetric multi-processor system, and more particularly, to a method and apparatus, in which an operating system migrates tasks from a current processor to another processor for load balancing in a symmetric multi-processor system.
2. Description of the Related Art
In processor architecture, a plurality of processors are loaded on one chip, and thus a plurality of tasks can be simultaneously performed. However, performance of a system cannot be proportionally improved by increasing the number of processors due to load imbalance, where tasks are not equally distributed and performed in all processors but instead, more tasks are assigned to a predetermined processor. Accordingly in order to solve such a problem, load balancing is required, where the balance of tasks assigned to each processor is adjusted by migrating tasks from a processor having a heavy load to another processor having a relatively light load.
FIG. 1 is a diagram illustrating a load balancing apparatus in a conventional symmetric multi-processor system, where two central processing units (CPUs) 110 and 120 are illustrated for convenience. The CPUs respectively include run queues 111 and 121, where tasks to be performed are stored. In FIG. 1, load balancing processes are achieved by a migration process 130, where tasks from the run queue 111 of the CPU 110, which has a heavy load with 5 tasks, to the run queue 121 of the CPU 120, which has a relatively light load with 2 tasks. In the migration process 130, a lock of the run queue 111, in which a current task is stored, is acquired first, and then a lock of the run queue 121, where the current task is to be migrated, is acquired. Here, a lock denotes an exclusive authority that disables a process from using a queue when another process is using the queue.
The reason for acquiring the locks and migrating the tasks in the run queues 111 and 121 is that integrity of the run queues 111 and 121 may be broken while adding or deleting a task in the run queues 111 and 121 while migrating the tasks, unless the locks of the run queues 111 and 121 are not acquired. When the integrity of the run queues 111 and 121 is broken, a certain task may be excluded from the run queues 111 and 121, and not be scheduled permanently. Also, the structure of the run queues 111 and 121 can be corrupted, and thus an operating system may crash. Such run queues 111 and 121 are objects having a mutual exclusion characteristic, where simultaneous use of one resource by a plurality of tasks is excluded, such as mutexes (mutual exclusion objects) or semaphores. In a mutex, a resource which can only be used by one task is expressed as a critical section. Accordingly, after migrating a task, the locks of the run queues 111 and 121 should be released so that other tasks can use the run queues 111 and 121. Acquiring and releasing a lock are performed as a pair, because when a lock for a certain task is not released after acquiring the lock, other tasks should wait endlessly. By simultaneously acquiring the locks of the run queues 111 and 121, the time taken to perform tasks is delayed, and as a result, performance of the operating system deteriorates.
FIG. 2 is a flowchart illustrating a load balancing method in a conventional symmetric multi-processor system. First, it is determined whether a load imbalance occurred in operation 201. If the load imbalance has occurred, a first CPU in which the load imbalance occurred, a second CPU, and a task that is to be migrated are selected in operation 202. An attempt is made to acquire a lock of a run queue of the first CPU in operation 203, and if the lock of the run queue of the first CPU is not acquired, the symmetric multi-processor system waits until it is acquired. If the lock of the run queue of the first CPU is acquired, operation 204 is performed. Similar to operation 203, an attempt is made to acquire a lock of a run queue of the second CPU in operation 204. If the locks of the run queues of the first and second CPUs are acquired, the task is migrated from the run queue of the first CPU to the run queue of the second CPU in operation 205. In operations 206 and 207, the locks of the run queues of the first and second CPUs are released.
FIG. 3 is a flowchart illustrating a method of scheduling load balancing in a conventional symmetric multi-processor system. In operation 301, a scheduler tries to acquire a lock of a run queue of a second CPU, and if the lock is not acquired, the scheduler waits until it is acquired. If the lock is acquired, a task to be performed next is selected according to a scheduling policy in operation 302. In operation 303, the lock of the run queue of the second CPU is released, and in operation 304, context switching, which involves switching a task that is currently being performed to the selected task, is performed.
The load balancing method in the conventional symmetric multi-processor system has been described with reference to FIGS. 2 and 3. Now, problems of the load balancing method will be described with reference to FIG. 4.
FIG. 4 is a diagram illustrating a sequence of performing tasks according to time while migrating the tasks in a conventional symmetric multi-processor system, and shows a scheduling delay due to a lock, as described above. Referring to FIG. 4, it is assumed that a task 410, a task 420, and a task 430 are respectively assigned to a CPU 1, a CPU 2, and a CPU 3, wherein a load of the task 430 is the lightest. When load imbalance occurs as assumed above, a scheduler determines to migrate the task 410 from the CPU 1 to the CPU 3. First, a lock of a run queue of the CPU 1, in which the task 410 is stored, is acquired, and then a lock of a run queue of the CPU 3, where the task 410 is to be migrated to, is acquired. At this time, the scheduler determines to migrate the task 420 from the CPU 2 to the CPU 3. Thus similarly, a lock of a run queue of the CPU 2, in which the task 420 is stored, is acquired, and then the lock of the run queue of the CPU 3, where the task 420 is to be migrated to, is acquired. However, the lock of the run queue of the CPU 3 has already been acquired by the task 410, at the time the task 420 requests to acquire the lock of the run queue of the CPU 3. Accordingly, the task 420 should wait in operation 440 until the lock of the run queue of the CPU 3 is released, and the lock of the run queue of the CPU 3 is again acquired for the task 420 after the lock of the run queue of the CPU 3 for the task 410 is released.
Meanwhile, when the scheduler schedules the task 430 of the run queue of the CPU 3, the lock of the run queue of the CPU 3 is already acquired for the tasks 410 and 420, and thus the task 430 should wait in operation 450 until the lock of the run queue of the CPU 3 is released. After the lock for the task 420 is released, the lock for the task 430 is acquired, and thus the task 430 is scheduled. Thus, in the load balancing method in a conventional multi-processor system, the scheduler waits for a long time due to contention to preoccupy a run queue, that is, contention to acquire a lock of a run queue. Accordingly, performance of the multi-processor system deteriorates, and response time of each task is remarkably delayed. Specifically, such a delay in the response time has a negative impact on guaranteeing of an immediate response in a real-time operating system, such as an embedded system.